๋ฌธ์
๐ Logic
class Node implements Comparable<Node> {
int to;
int weight;
int status;
public Node(int to, int weight, int status) {
this.to = to;
this.weight = weight;
this.status = status;
}
// ์ค๋ฆ์ฐจ์ ์ ๋ ฌ์ ์ํจ, ์ฌ๋ฌ ๊ฒฝ๋ก ์ค ์ต์ ๋น์ฉ์ ๋จผ์ ํ์ํ๊ธฐ ์ํจ
@Override
public int compareTo(Node n) {
return this.weight - n.weight;
}
}
- ์ต์ ๋น์ฉ์ ๊ตฌํ๊ธฐ ์ํด ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ๋๋ฐ, ๊ฐ์ค์น๋ฅผ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์ ์ ๋ ฌ์ ์ํด
compareTo()๋ฅผ ์ค๋ฒ๋ผ์ด๋ฉํ๋ค.
private void dijkstra(int s, int e) {
queue = new PriorityQueue<>();
dist[s][0] = 0;
queue.add(new Node(s, 0, 0));
while(!queue.isEmpty()) {
Node node = queue.poll();
int to = node.to;
int weight = node.weight;
int status = node.status;
if (to == e) return;
// ์ด๋ํ๋ ค๋ ๋
ธ๋๊ฐ ํธ๋ฉ์ธ์ง ํ์ธํ๊ณ , ํธ๋ฉ์ด๋ผ๋ฉด ์ด๋ฏธ ๋ฐ์ ํธ๋ฉ์ธ์ง ํ์ธ
// f = 0, ๋ฐ์ง ์์ ํธ๋ฉ์ด๊ฑฐ๋ ์ผ๋ฐ ๋
ธ๋ / f = 1, ์ด๋ฏธ ๋ฐ์ ํธ๋ฉ
int f = 0;
if (trapMap.containsKey(to)) {
if ((status & trapMap.get(to)) != 0)
f = 1;
}
forward(to, weight, status, f);
backward(to, weight, status, f);
}
}
- ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ์ฌ ํธ๋ฉ ์ฌ๋ถ์ ๋ฐ๋ผ
f๋ฅผ ์ง์ ํ๊ณ , ์ ๋ฐฉํฅ ํ์๊ณผ ์ญ๋ฐฉํฅ ํ์์ ์ํํ๋ค.
private void forward(int to, int weight, int status, int f) {
for (Node next : orgList[to]) {
canForward = f;
int nStatus = status;
if (trapMap.containsKey(next.to)) {
if ((status & trapMap.get(next.to)) != 0)
canForward ^= 1;
nStatus ^= trapMap.get(next.to);
}
if (canForward != 0) continue;
if (dist[next.to][status] > weight + next.weight) {
dist[next.to][status] = weight + next.weight;
queue.add(new Node(next.to, dist[next.to][status], nStatus));
}
}
}
-
์ ๋ฐฉํฅ ํ์์ ๊ฒฝ์ฐ,
- ๋ค์ ๋ฐฉ๋ฌธํ ๋ ธ๋์ ํธ๋ฉ ์ฌ๋ถ๋ฅผ ํ์ธํ๊ณ ,
- ํธ๋ฉ์ธ ๊ฒฝ์ฐ, ํธ๋ฉ์ ๋ฐ๋ ์ฌ๋ถ๋ฅผ ํ์ธํ๋ค.
canForward๊ฐ0์ธ ๊ฒฝ์ฐ(์ฆ, ํธ๋ฉ์ด์ง๋ง ํ์ฑํ ๋์ง ์์๊ฑฐ๋ ์ผ๋ฐ ๋ ธ๋์ธ ๊ฒฝ์ฐ)๋งqueue์ ํด๋น ์ง์ ์ ์ถ๊ฐํ๋ค.- 0์ธ ๊ฒฝ์ฐ: (f:canForward = 0:0 or 1:1)
- ์ญ๋ฐฉํฅ์ ๋ฐ๋
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Node implements Comparable<Node> {
int to;
int weight;
int status;
public Node(int to, int weight, int status) {
this.to = to;
this.weight = weight;
this.status = status;
}
// ์ค๋ฆ์ฐจ์ ์ ๋ ฌ์ ์ํจ, ์ฌ๋ฌ ๊ฒฝ๋ก ์ค ์ต์ ๋น์ฉ์ ๋จผ์ ํ์ํ๊ธฐ ์ํจ
@Override
public int compareTo(Node n) {
return this.weight - n.weight;
}
}
class Maze {
List<Node>[] orgList;
List<Node>[] reverseList;
Map<Integer, Integer> trapMap;
Queue<Node> queue;
int[][] dist;
int canForward = 0;
public Maze(int n, int[][] roads, int[] traps) {
// List ์ด๊ธฐํ
orgList = new ArrayList[n + 1];
reverseList = new ArrayList[n + 1];
initList(n);
fillList(roads);
// ํธ๋ฉ ์ด๊ธฐํ(์ขํ ์์ถ์ ํตํด 2,5,10 -> 1,2,3์ผ๋ก ์ ์ฅ)
trapMap = new HashMap<>();
initTrap(traps);
dist = new int[n+1][1<<trapMap.size()+1];
initDist(n);
}
private void initList(int n) {
for (int i = 0; i < n + 1; i++) {
orgList[i] = new ArrayList<>();
reverseList[i] =new ArrayList<>();
}
}
// ์ด๊ธฐ ๊ฒฝ๋ก์, ํธ๋ฉ์ผ๋ก ์ธํด ๋ฐ๋๋ก ์ ํ๋๋ ๊ฒฝ๋ก๋ฅผ ์ ์ฅ
private void fillList(int[][] roads) {
for (int[] road : roads) {
int from = road[0];
int to = road[1];
int weight = road[2];
orgList[from].add(new Node(to, weight, 0));
reverseList[to].add(new Node(from, weight, 0));
}
}
// ์ขํ ์์ถ
private void initTrap(int[] traps) {
for (int i = 0; i < traps.length; i++)
trapMap.put(traps[i], 1 << (i + 1));
}
private void initDist(int n) {
for (int i = 0; i < n + 1; i++) Arrays.fill(dist[i], Integer.MAX_VALUE);
}
public int solution(int start, int end) {
dijkstra(start, end);
int minCost = Integer.MAX_VALUE;
for (int d : dist[end])
minCost = Math.min(minCost, d);
return minCost;
}
private void dijkstra(int s, int e) {
queue = new PriorityQueue<>();
dist[s][0] = 0;
queue.add(new Node(s, 0, 0));
while(!queue.isEmpty()) {
Node node = queue.poll();
int to = node.to;
int weight = node.weight;
int status = node.status;
if (to == e) return;
// ์ด๋ํ๋ ค๋ ๋
ธ๋๊ฐ ํธ๋ฉ์ธ์ง ํ์ธํ๊ณ , ํธ๋ฉ์ด๋ผ๋ฉด ์ด๋ฏธ ๋ฐ์ ํธ๋ฉ์ธ์ง ํ์ธ
// f = 0, ๋ฐ์ง ์์ ํธ๋ฉ์ด๊ฑฐ๋ ์ผ๋ฐ ๋
ธ๋ / f = 1, ์ด๋ฏธ ๋ฐ์ ํธ๋ฉ
int f = 0;
if (trapMap.containsKey(to)) {
if ((status & trapMap.get(to)) != 0)
f = 1;
}
forward(to, weight, status, f);
backward(to, weight, status, f);
}
}
// orgList = ์ ๋ฐฉํฅ์ ๋ํ ํ์
private void forward(int to, int weight, int status, int f) {
for (Node next : orgList[to]) {
canForward = f;
int nStatus = status;
if (trapMap.containsKey(next.to)) {
if ((status & trapMap.get(next.to)) != 0)
canForward ^= 1;
nStatus ^= trapMap.get(next.to);
}
if (canForward != 0) continue;
if (dist[next.to][status] > weight + next.weight) {
dist[next.to][status] = weight + next.weight;
queue.add(new Node(next.to, dist[next.to][status], nStatus));
}
}
}
// reverseList = ์ญ๋ฐฉํฅ์ ๋ํ ํ์
private void backward(int to, int weight, int status, int f) {
for (Node next : reverseList[to]) {
canForward = f;
int nStatus = status;
if (trapMap.containsKey(next.to)) {
if ((status & trapMap.get(next.to)) != 0)
canForward ^= 1;
nStatus ^= trapMap.get(next.to);
}
if (canForward != 1) continue;
if (dist[next.to][status] > weight + next.weight) {
dist[next.to][status] = weight + next.weight;
queue.add(new Node(next.to, dist[next.to][status], nStatus));
}
}
}
}
class Solution {
public int solution(int n, int start, int end, int[][] roads, int[] traps) {
Maze m = new Maze(n, roads, traps);
return m.solution(start, end);
}
}
โ๏ธ Review
- ์์์ง์ ๋ถํฐ ์ข
๋ฃ์ง์ ๊น์ง์ ํ์์ ์ํ ๊ทธ๋ํ ํ์ ์๊ณ ๋ฆฌ์ฆ๊ณผ, ํธ๋ฉ์ ๋ฐฉ๋ฌธํ ๊ฒฝ์ฐ ์ฐ๊ฒฐ๋ ๊ธธ์
Switchingํด์ฃผ๋ ์๊ณ ๋ฆฌ์ฆ์ด ํ์ํ๋ค. - ๊ทธ๋ํ ํ์์ DFS๋ BFS๋ฅผ ์ฌ์ฉํ ์ ์์ง๋ง, ์ฐ๊ฒฐ๋ ๊ธธ์ ๋ํ
Switching์ ์ด๋ป๊ฒ ํด์ผํ ์ง ๊ฐ์ด ์ค์ง ์์๋ค. ๊ธธ์ ๋น์ฉ์ ๊ณ ์ ์ ์ด์ง๋ง, ๋ฐฉํฅ๋ง ๋ฐ๊ฟ์ค์ผ ํ๋ค. - ์ฐธ๊ณ ๋ธ๋ก๊ทธ๋ฅผ ๋ณด๋ฉด์ ์ดํดํ๋๋ฐ, "๊ธฐ๋ณธ์ ์ธ ๋ก์ง์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๊ฒ์ด๋ค. ๋ํ ์กฐ๊ฑด์ ๋ ์ง์ ๊ฐ ์ฌ๋ฌ ๊ธธ์ด ์กด์ฌํ ์ ์๊ณ , ๊ธธ๋ง๋ค์ ๊ฐ์ค์น๊ฐ ์๊ธฐ์, ๊ทธ๋์ ๋๊ฐ์ ๊ฒฝ๋ก๋ผ ํ๋๋ผ๋ ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ์ง ๊ฐ์ ์ ์์ฃผ๋ก ํ์์ ํด์ผํ๋ฏ๋ก ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ ๋ค์ต์คํธ๋ผ๊ฐ ๋ฌธ์ ์ ๋ณธ์ง์์ ์์๋ผ ์ ์๋ค." ์ด๋ฌํ ์๊ฐ์ ํ ์ ์๋๋ก ๋ ธ๋ ฅํด์ผ ๊ฒ ๋ค.
- ๋นํธ๋ง์คํน์ ์ฌ์ฉํ ํ์ด๋ฅผ ์ฐธ๊ณ ํ๋๋ฐ, ์ฝ๋๋ฅผ ๋ณด๊ณ ๋ด๋ ์ดํด๊ฐ ์ด๋ ค์ด ๊ฒ ๊ฐ๋ค. ์์ฃผ ์ฌ์ฉํด๋ณด์ง ์์ ์๊ณ ๋ฆฌ์ฆ์ด์ด์ ๊ทธ๋ฐ ๊ฒ ๊ฐ๋ค. ๋นํธ๋ง์คํน์ ์ฌ์ฉํ๋ ๊ธฐ๋ณธ ์์ ๋ฅผ ํ์ด๋ด์ผ๊ฒ ๋ค.
๐ ์ฐธ๊ณ
[ํ๋ก๊ทธ๋๋จธ์ค] 2021 ์นด์นด์ค ์ธํด #4 ๋ฏธ๋ก ํ์ถ (Java)